package 栈;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @author liucong
 * @date 2021/2/23 - 16:56
 *
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 *
 * 有效字符串需满足：
 *
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 *  
 *
 * 示例 1：
 *
 * 输入：s = "()"
 * 输出：true
 * 示例 2：
 *
 * 输入：s = "()[]{}"
 * 输出：true
 * 示例 3：
 *
 * 输入：s = "(]"
 * 输出：false
 * 示例 4：
 *
 * 输入：s = "([)]"
 * 输出：false
 * 示例 5：
 *
 * 输入：s = "{[]}"
 * 输出：true
 *  
 *
 * 提示：
 *
 * 1 <= s.length <= 104
 * s 仅由括号 '()[]{}' 组成
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/valid-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _20_有效的括号 {
    public static void main(String[] args) {
        System.out.println(isValid1("{[]}"));
        System.out.println(isValid2("{[]}"));
    }

    public static boolean isValid3(String s) {
        Map<Character,Character> map=new HashMap<>();
        map.put('[',']');
        map.put('(',')');
        map.put('{','}');

        Stack<Character> stack=new Stack<>();
        int len=s.length();
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if(map.containsKey(c)){ //左括号
                stack.push(c);
            }else{ //右括号
                if(stack.isEmpty()) return false;

                char left = stack.pop();
                if(map.get(left) != c) return false;
            }
        }

        return stack.isEmpty();
    }

    /*
    1.遇见左括号，入栈
    2.遇见右括号
        如果栈是空的，括号无效
        如果栈不为空，将栈顶括号出栈，与右括号匹配
            不匹配，括号无效
            匹配，继续扫描下一个
    3.所有字符扫描完毕
        栈为空，括号有效
        栈不为空，括号无效
     */
    public static boolean isValid2(String s) {
        Stack<Character> stack=new Stack<>();
        int len=s.length();
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if(c == '[' || c== '{' || c == '('){ //左括号
                stack.push(c);
            }else{ //右括号
                if(stack.isEmpty()) return false;

                char left = stack.pop();
                if(left == '(' && c != ')') return false;
                if(left == '{' && c != '}') return false;
                if(left == '[' && c != ']') return false;
            }
        }

        return stack.isEmpty();
    }

    public static boolean isValid1(String s) {
        while(s.contains("()")||s.contains("[]")||s.contains("{}")){
            s=s.replace("()","");
            s=s.replace("[]","");
            s=s.replace("{}","");
        }
        return s.isEmpty();
    }
}
